#该文件实现 输入文法的化简 和 消除 左递归 提左因子

#消除直接左递归
#文法使用的数据结构
#需求：字典+列表
#文法的输入方式
#输入文法的方式
#终结符集合，非终结符集合，开始符号，产生式集合

#PPT总控程序测试 i*i+i
# pa = "E->TA A->+TA|ε T->FB B->*FB|ε F->(E)|i"
# tsym = {"E","A","T","B","F"}
# nsym = {'ε','i','(','*','+',')'}
# start = 'E'

#无
# pa = "E->TA A->+E|ε T->FB B->T|ε F->PC C->*C|ε P->(E)|a|b|^"
# tsym = {"E","A","T","B","F","C","P"}
# nsym = {'ε','a','b','^','(','*','+',')'}
# start = 'E'

#消除直接左递归例子
# nsym = {'a','^','(',')',','}
# tsym = {'T','S'}
# pa = "S->a|^|(T) T->T,S|S|T)"
# start = 'T'

#消除间接左递归例子 bcabc
# nsym = {'c','b','a'}
# tsym = {'S','Q','R'}
# pa = "S->Qc|c Q->Rb|b R->Sa|a"
# start = 'S'

#消除直接左递归例子，提供左因子
pa = "T->TE E->ε A->ε T->Ta T->TAb T->TAc"
tsym = {"E","A","T"}
nsym = {'ε','a','b','c'}
start = 'T'

import copy

class grammar:
    Nsym = set() #非终结符集合
    Tsym = set() #终结符集合
    Ssym = ''
    Pattern = {} #产生式集合，字典+列表
    FIRST = {}
    FOLLOW = {}
    ANALYSIS_TABLE = {}
    SELECT = {}
    ENVENTUALLIST = []

    def __init__(self,_Nsym,_Tsym,_Ssym,_Pattern):
        self.Tsym = _Tsym
        self.Nsym = _Nsym
        self.Ssym = _Ssym
        #化简pattern
        #要求输入的pattern是字符串
        #每行是一个表达式
        #先把他们按照行来分开
        patterns = _Pattern.split(' ')
        #先去箭头,消除或符号
        for p in patterns:
            nsym = p.split('->')
            if self.Pattern.get(nsym[0]) == None:
                self.Pattern.update({nsym[0]:nsym[1].split('|')})
            else:
                self.Pattern[nsym[0]].extend(nsym[1].split('|'))
        # print('***初始化***',self.Pattern)
    def find_commonprefix(self,s1:str,s2:str):
        lens = min(len(s1),len(s2))
        for i in range(lens):
            if s1[i] != s2[i]:
                return [s1[:i],i]
        return [s1,lens]
    def judje_extract(self):
        for k,vl in self.Pattern.items():
            lens = len(vl)
            for i in range(lens):
                for j in range(i+1,lens):
                    nowa = self.find_commonprefix(vl[i],vl[j])
                    if len(nowa) and nowa[1]:
                        return True
        return False
    def extract(self):
        if not self.judje_extract():
            # print(self.Pattern)
            return
        patterns = copy.deepcopy(self.Pattern)
        for k,vl in self.Pattern.items():
            lens = len(vl)
            anst = []
            for i in range(lens):
                for j in range(i+1,lens):
                    nowa = self.find_commonprefix(vl[i],vl[j])
                    if nowa[1] and (not anst or anst[1] > nowa[1]):
                        anst = nowa
                #把里面的重复的删掉
                #添加上替换的
            if len(anst):
                deleteset,leftset = set(),set()
                for alpha in vl:
                    strrs = self.find_commonprefix(anst[0],alpha)
                    if strrs[0] == anst[0]:
                        deleteset.add(alpha)
                        leftset.add(alpha[anst[1]:])
                # print(deleteset,leftset)
                alphabet = [chr(i + ord('A')) for i in range(26) if chr(i + ord('A')) not in self.Tsym]
                for i in deleteset:
                    patterns[k].remove(i)
                patterns[k].append(anst[0] + alphabet[0])
                self.Tsym.add(alphabet[0])
                for i in leftset:
                    if patterns.get(alphabet[0]) != None:
                        patterns[alphabet[0]].append(i)
                    else:
                        patterns[alphabet[0]] = [i]
        self.Pattern = patterns
        self.extract()


    def reshape_alpha(self,sym,alphas,betas):
        """
        :param sym:
        :param alpha:
        :param beta:
        :return:
        """
        if not alphas or not betas:
            return
        alphabet = [chr(i + ord('A')) for i in range(26) if chr(i + ord('A')) not in self.Tsym]
        for beta in betas:
            self.Pattern[sym].append(beta+alphabet[0])
        self.Pattern[alphabet[0]] = []
        for alpha in alphas:
            self.Pattern[alphabet[0]].append(alpha[1:]+alphabet[0])
        self.Pattern[alphabet[0]].append('ε')
        self.Tsym.add(alphabet[0])
        for alpha in alphas:
            self.Pattern[sym].remove(alpha)
        for beta in betas:
            self.Pattern[sym].remove(beta)

    def EDLR_ONE(self,k,vl):
        alphas,betas = [],[]
        for index, alpha in enumerate(vl):
            if k == alpha[0]:
                alphas.append(alpha)
            else:
                betas.append(alpha)
        print(alphas,betas)
        self.reshape_alpha(k, alphas, betas)

    def EDLR_ALL(self):
        newPattern = copy.deepcopy(self.Pattern)
        for k,vl in newPattern.items():
            self.EDLR_ONE(k,vl)
        # print('***消除直接左递归***',self.Pattern)

    def replace_nsym(self,k,alpha_real):
        for substitution in self.Pattern[alpha_real[0]]:
            self.Pattern[k].append(alpha_real.replace(alpha_real[0],substitution))
        self.Pattern[k].remove(alpha_real)

    def EIDLR(self):
        newPattern = copy.deepcopy(self.Pattern)
        for i in range(len(self.Tsym)):
            for k,vl in newPattern.items():
                sortList = list(self.Tsym) #?
                sortList.sort() #?
                for alpha in vl:
                    if alpha[0] in self.Tsym and sortList.index(k) > sortList.index(alpha[0]):
                        self.replace_nsym(k,alpha)
                        del self.Pattern[alpha[0]]
                self.EDLR_ONE(k,vl)
            newPattern = copy.deepcopy(self.Pattern)
        #更新下集合
        self.Tsym = {k for k in self.Pattern}
        # print('***消除循环左递归***',self.Pattern)

    def DOFISRT(self):
        self.FIRST = {i : set() for i in self.Tsym}
        pattern = self.Pattern
        # print(pattern)
        def recursion_find(target): #返回target的FIRST集合
            for alpha in pattern[target]:
                if alpha != 'ε' and alpha[0] in self.Nsym:
                    self.FIRST[target].add(alpha[0])
                elif alpha[0] in self.Tsym and self.FIRST[alpha[0]]:
                    self.FIRST[target].update(self.FIRST[alpha[0]])
                elif alpha[0] in self.Tsym:
                    index = 0
                    while alpha[index] in self.Tsym and 'ε' in pattern[alpha[index]]:
                        index += 1
                    if index == len(alpha):
                        self.FIRST[target].add('ε')
                    else:
                        self.FIRST[target].update(recursion_find(alpha[index]))
                elif alpha == 'ε':
                    self.FIRST[target].add('ε')
            return self.FIRST[target]
        for i in self.Tsym: recursion_find(i)
        print('***FIRST集合为***',self.FIRST)
        return self.FIRST


    def DOFOLLOW(self):
        self.FOLLOW = { i : set() for i in self.Tsym}
        def recursion_find(target):
            if self.FOLLOW[target] : return self.FOLLOW[target]
            if target == self.Ssym: self.FOLLOW[target].add('#')
            for k,vl in self.Pattern.items():
                for alpha in vl:
                    if alpha == 'ε': continue
                    id,lalpha = 0,len(alpha)
                    while id < lalpha - 1:
                        if alpha[id] != target:
                            id += 1
                            continue
                        if alpha[id + 1] in self.Nsym:
                            self.FOLLOW[target].add(alpha[id + 1])
                            break #感觉要写一个，否则可能出错
                        elif alpha[id + 1] in self.Tsym :
                            index = id + 1
                            while index < lalpha:
                                if 'ε' in self.FIRST[alpha[index]]:
                                    self.FOLLOW[target].update(self.FIRST[alpha[index]]-{'ε'})
                                else:
                                    self.FOLLOW[target].update(self.FIRST[alpha[index]])
                                    break
                                index += 1
                            if index == lalpha:
                                self.FOLLOW[target].update(recursion_find(k))
                        id += 1
                    if alpha[-1] == target:
                        self.FOLLOW[target].update(recursion_find(k))
            return self.FOLLOW[target]
        for i in self.Tsym: recursion_find(i)
        print('***FOLLOW集合为***',self.FOLLOW)
        return self.FOLLOW


    def DOFIRSTALPHA(self,vl):
        FIRST_alphas = {i: set() for i in vl}
        for id,alpha in enumerate(vl):
            for sym in alpha:
                if alpha == 'ε': continue
                if sym in self.Tsym and 'ε' not in self.Pattern[sym]:
                    FIRST_alphas[alpha].update(self.FIRST[sym])
                    break
                elif sym in self.Tsym:
                    FIRST_alphas[alpha].update(self.FIRST[sym])
                    if id == len(vl) - 1:
                        FIRST_alphas[alpha].add('ε')
                elif sym in self.Nsym :
                    FIRST_alphas[alpha].add(sym)
                    break
        # print(FIRST_alphas)
        return FIRST_alphas

    def DOSELECT(self):
        for k,vl in self.Pattern.items():
            for alpha in vl:
                self.SELECT[(k,alpha)] = set()
        for k,vl in self.Pattern.items():
            FIRSTALPHAS = self.DOFIRSTALPHA(vl)
            for ALPHA,FIRSTALPHA in FIRSTALPHAS.items():
                if ALPHA == 'ε':
                    self.SELECT[(k, ALPHA)].update(FIRSTALPHA - {'ε'})
                    self.SELECT[(k, ALPHA)].update(self.FOLLOW[k])
                elif 'ε' not in FIRSTALPHA:
                    self.SELECT[(k,ALPHA)].update(FIRSTALPHA)
                else:
                    self.SELECT[(k, ALPHA)].update(FIRSTALPHA - {'ε'})
                    self.SELECT[(k, ALPHA)].update(self.FOLLOW[k])
        # print('***SELECT***',self.SELECT)
        # print(str(self.SELECT))
        return self.SELECT

    def judge_LLOne(self):
        '''
        这个算法需要你满足三个条件
        1. 每个非终结符的FIRST集不相交
        2. 如果\ε \in FIRST ,那么要求 这个非终结符的FIRST集合和FOLLOW集合不相交
        3. 不存在左递归的情况
        :return:
        '''
        #第一部分:去判断这个文法是不是含有左递归
        def judge_left_recursion(target,sym):
            if sym in self.Nsym: return True
            ans = True
            for alpha in self.Pattern[sym]:
                if alpha[0] == sym or alpha[0] == target:
                    return False
                if alpha[0] in self.Tsym:
                    ans = ans and judge_left_recursion(target,alpha[0])
            return ans
        for i in self.Tsym:
            if not judge_left_recursion(i,i):
                return False
        #第二部分:去判断每个非终结符的候选式的 FOLLOW集不相交
        for k,vl in self.Pattern.items():
            FIRST_alphas = self.DOFIRSTALPHA(vl)
            #用并查集可以快速判断，这里直接暴力算法了
            FIRST_alphas_list = []
            for k,v in FIRST_alphas.items():
                FIRST_alphas_list.append(v)
            original_set = copy.deepcopy(FIRST_alphas_list[0])
            if len(FIRST_alphas_list) > 1:
                for set_alpha in FIRST_alphas_list[1:]:
                    for i in set_alpha:
                        if i in original_set:
                            return False
                        else:
                            original_set.add(i)
        #第三部分:判断每个非终结符的FOLLOW集不相交
        for i in self.Tsym:
            if 'ε' in self.FIRST[i] and self.FIRST[i] & self.FOLLOW[i]:
                return False
        return True

    def TableOFANALYSIS(self):
        for (l,r),v in self.SELECT.items():
            for sym in v:
                self.ANALYSIS_TABLE[(l,sym)] = r
        print('***分析预测表***',self.ANALYSIS_TABLE)
    def lts(self,l):
        s = ''
        for i in l: s+=i
        return s
    def PredictAnalysis(self,match):
        '''
        :param match: 待匹配的句子
        :return: bool
        1. 把SELECT转化为表
        2. 进行操作
        '''
        self.TableOFANALYSIS()
        smatch = match+'#'
        stk = ['#',self.Ssym]
        count = 0
        self.ENVENTUALLIST.append(f'{count:<3}{self.lts(stk):<10}{smatch:<10}NULL      initialize')
        count += 1
        for i in range(len(smatch)):
            c = smatch[i]
            while c != stk[-1]:
                top = stk[-1]
                if self.ANALYSIS_TABLE.get((top,c)) != None:
                    stk.pop()
                    nextstr = self.ANALYSIS_TABLE.get((top,c))
                    s1 = f'{top}->{nextstr}'
                    if nextstr != 'ε':
                        sequence = [c for c in self.ANALYSIS_TABLE[(top, c)]]
                        sequence.reverse()
                        stk.extend(sequence)
                        self.ENVENTUALLIST.append(f'{count:<3}{self.lts(stk):<10}{smatch[i:]:<10}{s1:<10}POP,PUSH{self.lts(sequence)}')
                        count += 1
                    else:
                        self.ENVENTUALLIST.append(f'{count:<3}{self.lts(stk):<10}{smatch[i:]:<10}{s1:<10}POP')
                        count += 1
                else:
                    return [[],False]
            if stk[-1] == c and c == '#':
                return [self.ENVENTUALLIST,True]
            elif stk[-1] == c and c != '#':
                s1 = f'{top}->{nextstr}'
                self.ENVENTUALLIST.append(f'{count:<3}{self.lts(stk):<10}{smatch[i:]:<10}{s1:<10}GETNEXT')
                count += 1
                stk.pop()
        # print('ENVENTUAL',self.ENVENTUALLIST)



    def formatgrammar(self):
        s1 = 'VN    '
        for i in self.Tsym: s1 = s1 + i + ' '
        s2 = 'VT    '
        for i in self.Nsym: s2 = s2 + i + ' '
        s3 = 'P     '
        for k,vl in self.Pattern.items():
            temp = ''
            for alpha in vl:
                temp = temp + alpha + '|'
            temp = temp[:-1]
            s3 = s3 + str(k) +'->' +temp+' '
        # print([s1,s2,f'S    {self.Ssym}',s3])
        return s1 + '\n' + s2 + '\n' + f'S     {self.Ssym}' + '\n' + s3

    def formatSet(self,first = False,follow = False,select = False,analysis = False):
        waitset = None
        if first == True:
            waitset = self.FIRST
        elif follow == True:
            waitset = self.FOLLOW
        elif select == True:
            waitset = self.SELECT
        elif analysis == True:
            waitset = self.ANALYSIS_TABLE
        ans = ''
        for k,v in waitset.items():
            ans += f'{k:<10}{v:<10}'
            ans += '\n'
        return ans

g = grammar(nsym,tsym,start,pa)
# g.EDLR_ALL()
# g.EIDLR()
# g.EIDLR()
# g.DOFISRT()
# g.DOFOLLOW()
# g.DOSELECT()
# g.formatgrammar()
# g.start_up()
# print(g.PredictAnalysis('bcabc'))

# g.extract()
# g.EDLR_ALL()
# g.DOFISRT()
# g.DOFOLLOW()
# g.DOSELECT()
# print(g.judge_LLOne())